// 力扣91. 解码方法
import java.util.*;

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        // dp[i] 表示前i个字符的解码方式数量
        int[] dp = new int[n + 1];

        // 空字符串有1种解码方式（解码为空）
        dp[0] = 1;

        // 第一个字符的解码方式
        dp[1] = s.charAt(0) == '0' ? 0 : 1;

        // 填充dp数组
        for (int i = 2; i <= n; i++) {
            // 检查单个字符是否有效（1-9）
            char single = s.charAt(i - 1);
            if (single != '0') {
                dp[i] += dp[i - 1];
            }

            // 检查两个字符组成的数字是否有效（10-26）
            String twoDigits = s.substring(i - 2, i);
            int num = Integer.parseInt(twoDigits);
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}
// 力扣91. 解码方法 解法二:
class Solution1 {
    // 记忆化缓存，存储从index开始的子串的解码方式数量
    private Integer[] memo;

    public int numDecodings(String s) {
        int n = s.length();
        memo = new Integer[n];
        // 从索引0开始计算整个字符串的解码方式
        return dfs(s, 0);
    }

    // 计算从index开始的子串的解码方式数量
    private int dfs(String s, int index) {
        int n = s.length();

        //  base case：已经处理完所有字符，说明找到一种有效解码方式
        if (index == n) {
            return 1;
        }

        // 如果当前位置是'0'，无法单独解码，返回0
        if (s.charAt(index) == '0') {
            return 0;
        }

        // 查看缓存，如果已经计算过则直接返回
        if (memo[index] != null) {
            return memo[index];
        }

        // 情况1：只解码当前单个字符（1-9）
        int res = dfs(s, index + 1);

        // 情况2：如果剩余字符数 >= 2，尝试解码当前和下一个字符组成的两位数（10-26）
        if (index + 1 < n) {
            int twoDigits = Integer.parseInt(s.substring(index, index + 2));
            if (twoDigits >= 10 && twoDigits <= 26) {
                res += dfs(s, index + 2);
            }
        }

        // 将结果存入缓存
        memo[index] = res;
        return res;
    }
}





// 力扣93. 复原 IP 地址
class Solution2 {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        char[] ch = s.toCharArray();
        // 剪枝：IP地址长度范围是4-12位
        if (ch.length < 4 || ch.length > 12) {
            return ans;
        }
        StringBuilder temp = new StringBuilder();
        dfs(ch, ans, temp, 0, 0);
        return ans;
    }

    // 参数说明：
    // ch: 字符数组
    // ans: 结果集
    // path: 当前路径
    // start: 起始索引
    // time: 已添加的段数（0-4）
    public void dfs(char[] ch, List<String> ans, StringBuilder path, int start, int time) {
        // 终止条件：已分成4段且用完所有字符
        if (time == 4) {
            if (start == ch.length) {
                ans.add(path.toString());
            }
            return;
        }

        // 记录当前路径长度，用于回溯
        int len = path.length();

        // 尝试截取1-3位作为一段
        for (int i = 1; i <= 3; i++) {
            // 超出字符范围，停止尝试
            if (start + i > ch.length) {
                break;
            }

            // 截取当前段（从start开始，长度i）
            int num = 0;
            boolean hasLeadingZero = false;
            for (int j = 0; j < i; j++) {
                // 检查前导零（长度>1且首字符为'0'）
                if (i > 1 && j == 0 && ch[start + j] == '0') {
                    hasLeadingZero = true;
                    break;
                }
                num = num * 10 + (ch[start + j] - '0'); // 正确转换字符为数字
            }

            // 跳过有前导零或数值超出0-255范围的段
            if (hasLeadingZero || num > 255) {
                break;
            }

            // 添加到路径（第一段不加'.'，后续段加）
            if (time > 0) {
                path.append('.');
            }
            path.append(num);

            // 递归处理下一段
            dfs(ch, ans, path, start + i, time + 1);

            // 回溯：恢复路径到添加前的状态
            path.setLength(len);
        }
    }
}


